home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / standards / sgml / nist / parse2b / detutil.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-13  |  20.7 KB  |  525 lines
  1. /* National Institute of Standards and Technology (NIST)
  2. /* National Computer System Laboratory (NCSL)
  3. /* Office Systems Engineering (OSE) Group
  4. /* ********************************************************************
  5. /*                            D I S C L A I M E R
  6. /*                              (March 8, 1989)
  7. /*  
  8. /* There is no warranty for the NIST NCSL OSE SGML parser and/or the NIST
  9. /* NCSL OSE SGML parser validation suite.  If the SGML parser and/or
  10. /* validation suite is modified by someone else and passed on, NIST wants
  11. /* the parser's recipients to know that what they have is not what NIST
  12. /* distributed, so that any problems introduced by others will not
  13. /* reflect on our reputation.
  14. /* 
  15. /* Policies
  16. /* 
  17. /* 1. Anyone may copy and distribute verbatim copies of the SGML source
  18. /* code as received in any medium.
  19. /* 
  20. /* 2. Anyone may modify your copy or copies of SGML parser source code or
  21. /* any portion of it, and copy and distribute such modifications provided
  22. /* that all modifications are clearly associated with the entity that
  23. /* performs the modifications.
  24. /* 
  25. /* NO WARRANTY
  26. /* ===========
  27. /* 
  28. /* NIST PROVIDES ABSOLUTELY NO WARRANTY.  THE SGML PARSER AND VALIDATION
  29. /* SUITE ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
  30. /* EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  31. /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  32. /* THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS
  33. /* WITH YOU.  SHOULD THE SGML PARSER OR VALIDATION SUITE PROVE DEFECTIVE,
  34. /* YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
  35. /* 
  36. /* IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL NIST BE LIABLE FOR
  37. /* DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
  38. /* INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
  39. /* INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA
  40. /* BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A
  41. /* FAILURE OF THE PROGRAM TO OPERATE WITH PROGRAMS NOT DISTRIBUTED BY
  42. /* NIST) THE PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF
  43. /* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  44. */
  45.  
  46. /************************************************************************/
  47. /*   TITLE:          SGML PARSER                                        */
  48. /*   SYSTEM:         DTD PROCESSOR                                      */
  49. /*   SUBSYSTEM:                                                         */
  50. /*   SOURCE FILE:    DETUTIL.C                                          */
  51. /*   AUTHOR:         Michael Garris                                     */
  52. /*                                                                      */
  53. /*   DATE CREATED:                                                      */
  54. /*   LAST MODIFIED:                                                     */
  55. /*                                                                      */
  56. /*                  REVISIONS                                           */
  57. /*   WHEN      WHO            WHY                                       */
  58. /************************************************************************/
  59. #include <stdio.h>
  60. #include "detdefs.h"
  61. #include "detglbl.h"
  62. char *malloc();
  63. /************************************************************************/
  64. /************************************************************************/
  65. /* NESTLEVEL inputs an expression at "iptr" and calculates the number of*/
  66. /* nested levels of "()" in the expression, returning the calculation   */
  67. /************************************************************************/
  68. int nestlevel(iptr)
  69. register ITEM *iptr;/* points to the expression */
  70. {
  71.    register int nest = 0;/* nest level */
  72.    register int cntr = 0;/* current level */
  73.  
  74.    /* if iptr is not at a GRPO then a synchronization error has occurred */
  75.    if(iptr++->itoken != GRPO){
  76.       return(0);
  77.    }
  78.    /* otherwise a GRPO has been found and the nesting level gets bumped */
  79.    ++nest;
  80.    /* also a counter gets bumped for each GRPO found and decremented */
  81.    /* for each GRPC found */
  82.    ++cntr;
  83.    /* while the counter is not 0 ==> not at the end of the expression ...*/
  84.    while(cntr > 0){
  85.       /* while neither a GRPO or a GRPC has been found ...*/
  86.       while((iptr->itoken != GRPO) && (iptr->itoken != GRPC)){
  87.          /* if a FSAid pointer is found in the expression, skip it */
  88.          if(iptr->itoken == POINTER){
  89.             /* invokes a procedure which moves iptr the size of a pointer */
  90.             /*          commented out by Michael D. Garris on 11/23/87 */
  91.             /*          due to the introduction of ITEM type           */
  92.             /*            skippointer(&iptr);                          */
  93.             iptr += 2;
  94.             continue;
  95.          }
  96.          /* if not a pointer, GRPO, or GRPC then skip it */
  97.          ++iptr;
  98.       }
  99.       /* if a GRPO is found ... */
  100.       if(iptr->itoken == GRPO){
  101.          /* bump the nesting level */
  102.          ++nest;
  103.          /* bump the current level */
  104.          ++cntr;
  105.       }
  106.       /* if a GRPC is found ... */
  107.       if(iptr->itoken == GRPC){
  108.          /* decrement the current level */
  109.          --cntr;
  110.       }
  111.       /* continue looking in the expression */
  112.       ++iptr;
  113.    }
  114.    /* once the end of the expression is found, then return the */
  115.    /* value in nestin level */
  116.    return(nest);
  117. }
  118. /************************************************************************/
  119. /************************************************************************/
  120. /* GETLOWGRP takes an expression and scans it left to right until "nest"*/
  121. /* number of "(" have been found, setting the expression pointer to that*/
  122. /* location                                                             */
  123. /************************************************************************/
  124. void getlowgrp(ptrin, nest)
  125. ITEM **ptrin;
  126. register int nest;
  127. {
  128.    register ITEM *iptr = *ptrin;
  129.    register int i;
  130.  
  131.    for(i = 0; i < nest; ++i){
  132.       while(iptr++->itoken != GRPO);
  133.    }
  134.    *ptrin = --iptr;
  135. }
  136. /************************************************************************/
  137. /************************************************************************/
  138. /* SKIPPOINTER takes a pointer to a FSAid in an expression and moves the*/
  139. /* pointer to just past the FSAid pointer                               */
  140. /************************************************************************/
  141. void skippointer(ptrin)
  142. ITEM **ptrin;
  143. {
  144.    register ITEM *iptr = *ptrin;
  145.  
  146.    /* bump iptr by the size of a token, skipping the "-1" which */
  147.    /* is in font of all FSAid pointers in the expression */
  148.    ++iptr;
  149.    /* increment iptr the size of a pointer, skipping the actual */
  150.    /* FSAid pointer*/
  151.    ++iptr;
  152.    *ptrin = iptr;
  153. }
  154. /************************************************************************/
  155. /************************************************************************/
  156. /* GETTOKEN inputs a pointer to a token in an expression and returns the*/
  157. /* token, extracting the space occupied by the token from the expression*/
  158. /************************************************************************/
  159. int gettoken(iptr)
  160. register ITEM *iptr;
  161. {
  162.    register int token;
  163.  
  164.    /* if iptr is pointing to a valid token ...*/
  165.    if((iptr->itoken > 0x10) && (iptr->itoken < 0xFF))
  166.       /* then assign token what iptr is pointing to */
  167.       token = iptr->itoken;
  168.    else
  169.       /* otherwise a synchronization error has occurred */
  170.       myexit(1,"Token not found in group");
  171.    /* invokes a procedure which removes the space the size of an int */
  172.    /* from the expression at iptr */
  173.    stripunit(INT,iptr);
  174.    /* returns the token */
  175.    return(token);
  176. }
  177. /************************************************************************/
  178. /************************************************************************/
  179. /* GETOCCIND takes a pointer to an occurance indicator in an expression */
  180. /* and returns the occurance indicator, extracting the space occupied   */
  181. /* by the occurance indicator from the expression .                     */
  182. /************************************************************************/
  183. int getoccind(iptr)
  184. ITEM *iptr;
  185. {
  186.    int occind;
  187.  
  188.    switch(iptr->itoken){
  189.       /* if iptr points to an optional occurance indicator ...*/
  190.    case OPT:
  191.       occind = OPT;
  192.       break;
  193.       /* if iptr points to an optional-repeatable occ. indicator ...*/
  194.    case REP:
  195.       occind = REP;
  196.       break;
  197.       /* if iptr points to a required-repeatable occ. indicator ...*/
  198.    case PLUS:
  199.       occind = PLUS;
  200.       break;
  201.       /* if iptr points to a required occurance indicator ... */
  202.    case REQ:
  203.       occind = REQ;
  204.       break;
  205.    }
  206.    /* invokes a procedure which removes the space the size of an int */
  207.    /* from the expression at iptr */
  208.    stripunit(INT,iptr);
  209.    /* return the occurance indicator */
  210.    return(occind);
  211. }
  212. /************************************************************************/
  213. /************************************************************************/
  214. /* BUILDSTATE allocates memory for a structure called a state, returning*/
  215. /* a pointer to the allocated memory and setting all components of the  */
  216. /* structure to NULL.                                                   */
  217. /* A state is made of a left and right pointer pointing to other state  */
  218. /* structures, a left and right label marking each respective pointer,  */
  219. /* and a left and right instance number for each respective label.      */
  220. /************************************************************************/
  221. STATE *buildstate()
  222. {
  223.    register STATE *state;/* pointer memory will be allocated to */
  224.  
  225.    /* allocate memory to "state" the size of a state structure */
  226.    state = mymalloc(sizeof(STATE));
  227.    /* if malloc returned 0 then a memory allocation has occurred */
  228.    if(state == 0)
  229.       myexit(1, "Memory allocation error");
  230.    /* set all the fields of the components of the structure to NULL */
  231.    state -> lptr = NULL;
  232.    state -> llabel = NULL;
  233.    state -> linst = NULL;
  234.    state -> rptr = NULL;
  235.    state -> rlabel = NULL;
  236.    state -> rinst = NULL;
  237.    /* return a pointer to the allocated memory */
  238.    return(state);
  239. }
  240. /************************************************************************/
  241. /************************************************************************/
  242. /* BUILDID allocates memory to a structure called a FSAid, returning a  */
  243. /* pointer to the allocated memory and setting all components of the    */
  244. /* structure to NULL.                                                   */
  245. /* A FSAid is made of two pointers to state structures. The startptr    */
  246. /* points to the start state of an FSA, and the finalptr points to the  */
  247. /* final state of the same FSA.                                         */
  248. /************************************************************************/
  249. STATEID *buildid()
  250. {
  251.    register STATEID *stateid;
  252.  
  253.    /* allocate memory the size of a FSAid structure to the */
  254.    /* pointer "stateid" */
  255.    stateid = (STATEID *)malloc(sizeof(STATEID));
  256.    /* if malloc returns 0 then a memory allocation error occurred */
  257.    if(stateid == 0)
  258.       myexit(1,"Memory allocation error");
  259.    /* set both pointers of the FSAid structure to NULL */
  260.    stateid -> startptr = NULL;
  261.    stateid -> finalptr = NULL;
  262.    /* return the pointer to the allocated memory */
  263.    return(stateid);
  264. }
  265. /************************************************************************/
  266. /************************************************************************/
  267. /* INSERTPOINTER takes a pointer to a location within an expression and */
  268. /* inserts space for the inputted FSAid, placing the FSAid into the     */
  269. /* expression.                                                          */
  270. /************************************************************************/
  271. void insertpointer(ptrin,stateid)
  272. ITEM **ptrin;
  273. STATEID *stateid;
  274. {
  275.    register ITEM *iptr = *ptrin;
  276.  
  277.    /* invoke procedure to insert space the size of an int into */
  278.    /* the expression at location iptr */
  279.    makeroom(INT,iptr);
  280.    /* place a "-1" flagging, FSAid pointer following, */
  281.    /* into the expression */
  282.    iptr++->itoken = POINTER;
  283.    /* invokes a procedure to insert space the size of a FSAid */
  284.    /* pointer into the expression */
  285.    makeroom(PTR,iptr);
  286.    /* place the FSAid pointer into the expression */
  287.    iptr++->ptoken = stateid;
  288.    *ptrin = iptr;
  289. }
  290. /************************************************************************/
  291. /************************************************************************/
  292. /* MAKEROOM takes a pointer to an expression and insets space the size  */
  293. /* indicated by "type" at the location of the pointer.                  */
  294. /************************************************************************/
  295. void makeroom(type,iptr)
  296. int type;
  297. ITEM *iptr;
  298. {
  299.    int dif;
  300.    register int j;
  301.    register char *src, *dest;
  302.    char temp[400];
  303.  
  304.    /* assign "dif" the difference from the current location */
  305.    /* in the expression "iptr" to the end of the expression */
  306.    j = dif = (endbuf - iptr) * sizeof(ITEM);
  307.    /* move the section of expression from the current pointer on */
  308.    /* to the right the distance of "size" */
  309.    src = (char *) iptr;
  310.    dest = temp;
  311.    while (j--)
  312.       *dest++ = *src++;
  313.    src = temp;
  314.    dest = (char *)(iptr + 1);
  315.    while(dif--)
  316.       *dest++ = *src++;
  317. #ifdef OLD
  318.    memcpy((char *)(iptr + 1), (char *)iptr, dif);
  319. #endif
  320.    /* calculate a new end of expression */
  321.    endbuf++;
  322. }
  323. /************************************************************************/
  324. /************************************************************************/
  325. /* FINDENDOFGRP takes a pointer to the current location in an expression*/
  326. /* along with the current number of nested levels and scans to the right*/
  327. /* of the pointer until the end of the expression is found, retruning   */
  328. /* a pointer to the end of the expression.                              */
  329. /************************************************************************/
  330. ITEM *findendofgrp(iptr,nest)
  331. register ITEM *iptr;
  332. int nest;
  333. {
  334.    register int cntr;/* will be the current level of nesting */
  335.  
  336.    /* assign "cntr" the current level of nesting */
  337.    cntr = nest;
  338.    /* while current level of nesting is > 0 ==> not end of expression ...*/
  339.    while(cntr > 0){
  340.       /* while neither a GRPO or a GRPC is found ...*/
  341.       while((iptr->itoken != GRPO) && (iptr->itoken != GRPC)){
  342.          /* if iptr is pointing to an FSAid pointer ...*/
  343.          if(iptr->itoken == POINTER){
  344.             /* invokes a procedure to move the expression pointer */
  345.             /* just past the FSAid pointer */
  346.             iptr += 2;
  347.             /*            changed by Michael D. Garris 11/23/87        */
  348.             /*            commented out with the addition of ITEM type */
  349.             /*            skippointer(&iptr);                          */
  350.             continue;
  351.          }
  352.          /* continue looking right in expression */
  353.          ++iptr;
  354.       }
  355.       /* if GRPO found ...*/
  356.       if(iptr->itoken == GRPO){
  357.          /* bump nesting level and current nesting level */
  358.          ++nest;
  359.          ++cntr;
  360.       }
  361.       /* if GRPC found ...*/
  362.       if(iptr->itoken == GRPC){
  363.          /* decrement current nesting level */
  364.          --cntr;
  365.       }
  366.       /* continue scanning to the right */
  367.       ++iptr;
  368.    }
  369.    /* return pointer to end of expression */
  370.    return(iptr+1);
  371. }
  372. /************************************************************************/
  373. /************************************************************************/
  374. /* STRIPUNIT takes a pointer to an expression and removes a location the*/
  375. /* size indicated by "type" from the expression at the pointer          */
  376. /************************************************************************/
  377. void stripunit(type,iptr)
  378. int type;
  379. ITEM *iptr;
  380. {
  381.    int dif;
  382.  
  383.    /* assign "dif" the difference from the current expression */
  384.    /* pointer to the end of the expression */
  385.    dif = (endbuf - iptr + 1) * sizeof(ITEM);
  386.    /* move the section of expression from the current pointer plus */
  387.    /* the size of the unit being stripped on to the current pointer*/
  388.    memcpy((char *)iptr,(char *)(iptr + 1),dif);
  389.    /* calculate a new end of expression pointer */
  390.    endbuf -= 1;
  391. }
  392. /************************************************************************/
  393. /************************************************************************/
  394. /* COPY takes a section of expression at "scr" of length "len" and moves*/
  395. /* it to location "dest" in the expression.                             */
  396. /************************************************************************/
  397. void copy(dest,src,len)
  398. register char *dest,*src;
  399. register int len;
  400. {
  401.    /* if section being moved is to the right of the destination ...*/
  402.    if(src >= dest){
  403.       /* while "length" units have not yet been moved ...*/
  404.       while((len--) > 0){
  405.          /* copy contents of source to destination and continue */
  406.          *dest++ = *src++;
  407.       }
  408.    }
  409.    /* otherwise section being moved is to the left of the destination */
  410.    /* and a left to right transfer of contents could result in valid   */
  411.    /* data being over-written */
  412.    else{
  413.       /* if destination is to the right of the source ...*/
  414.       if(dest > src)
  415.          /* while "length" units have not yet been move ...*/
  416.          while(len-- > 0){
  417.             /* copy contents of source to destination right to left */
  418.             /* from the end of the source */
  419.             *(dest + len) = *(src + len);
  420.          }
  421.    }
  422. }
  423. /************************************************************************/
  424. /************************************************************************/
  425. /* GETCONNECTOR inputs a pointer to a connector in an expression and    */
  426. /* returns the connector, extracting the space occupied by the connector*/
  427. /* from the expression.                                                 */
  428. /************************************************************************/
  429. int getconnector(iptr)
  430. ITEM *iptr;
  431. {
  432.    int connector;
  433.  
  434.    /* assign "connector" the contents of the expression pointer */
  435.    connector = iptr->itoken;
  436.    /* invokes a procedure to extract the space of an int from */
  437.    /* the expression at location "iptr"*/
  438.    stripunit(INT,iptr);
  439.    /* returns the connector */
  440.    return(connector);
  441. }
  442. /************************************************************************/
  443. /************************************************************************/
  444. /* MYEXIT inputs an error code and an error message, printing the       */
  445. /* message and exiting on the error code.                               */
  446. /************************************************************************/
  447. void myexit(code,msg)
  448. int code;
  449. char *msg;
  450. {
  451.    printf("%s\n",msg);
  452.    exit(code);
  453. }
  454. /************************************************************************/
  455. /************************************************************************/
  456. /* SEARCHTOKEN searches a list of tokens,"tokseen", for matches on the  */
  457. /* value "token", returning the number of matches which occurred.       */
  458. /************************************************************************/
  459. int searchtoken(token,tokseen,tokptr)
  460. register int token;
  461. ITEM *tokseen,*tokptr;
  462. {
  463.    register ITEM *ptr = tokseen;/* set "ptr" to beginning of token list */
  464.    int inst = 0;/* will be the number of matches which occur */
  465.  
  466.    /* while not end of the token list ...*/
  467.    while(ptr != tokptr){
  468.       /* if a match on the "token" occurs...*/
  469.       if(ptr++->itoken == token)
  470.          /* bump the instance counter */
  471.          ++inst;
  472.    }
  473.    /* return the number of matches */
  474.    return(inst);
  475. }
  476. /************************************************************************/
  477. /************************************************************************/
  478. /****** M Y M A L L O C *************************************************/
  479. /*  this will create a linked list to track all malloc's ****************/
  480. /************************************************************************/
  481. STATE *mymalloc(size)
  482. int size;
  483. {
  484.    STATE *statetemp;
  485.    register MEMNODE *memtemp,*curmem;
  486.    curmem = head;
  487.    if ((statetemp = (STATE *)malloc(size)) == NULL) {
  488.       printf("Memory Allocation Error\n");
  489.       exit(99);
  490.    }
  491.    if ((memtemp = (MEMNODE *)malloc(sizeof(MEMNODE))) == NULL) {
  492.       printf("Memory Allocation Error\n");
  493.       exit(99);
  494.    }
  495.    (*memtemp).stateptr = statetemp;
  496.    (*memtemp).memnodeptr = NULL;
  497.    if ( head == NULL )
  498.       head = memtemp;   /* head is null; first time thru */
  499.    else {
  500.       while ( (*curmem).memnodeptr != NULL )
  501.          curmem = (*curmem).memnodeptr;  /* find the end of list */
  502.       (*curmem).memnodeptr = memtemp;
  503.    }
  504.    return((*memtemp).stateptr);
  505. }
  506. /************************************************************************/
  507. /** F R E E F S A *******************************************************/
  508. /************************************************************************/
  509. freeFSA()
  510. {
  511.    register MEMNODE *curmem,*temp;
  512.  
  513.    curmem = head;
  514.    if ( head == NULL )
  515.       return;
  516.    while ( curmem != NULL ){
  517.       temp = (*curmem).memnodeptr;
  518.       free((char *) ((*curmem).stateptr));
  519.       free((char *) curmem);
  520.       curmem = temp;
  521.    }
  522. }
  523. /************************************************************************/
  524.  
  525.